#include <iostream>

using namespace std;

const int N = 1e5 + 10;

// 创建双链表
int e[N], ne[N], pre[N], id, h;
int mp[N]; // mp[i] 表示：i 这个值存储的位置

// 遍历链表
void print()
{
    for(int i = ne[h]; i; i = ne[i])
    {
        cout << e[i] << " ";
    }
    cout << endl << endl;
}

// 头插
void push_front(int x)
{
    id++;
    e[id] = x;
    mp[x] = id;

    // 先修改新来结点的左右指针
    pre[id] = h;
    ne[id] = ne[h];

    // 修改哨兵位下一个结点的左指针
    pre[ne[h]] = id;
    ne[h] = id;
}

int find(int x)
{
    return mp[x];
}

// 在任意位置 p 的后面插入新的元素 x
void insert_back(int p, int x)
{
    id++;
    e[id] = x;
    mp[x] = id;

    pre[id] = p;
    ne[id] = ne[p];
    pre[ne[p]] = id;
    ne[p] = id;
}

// 在任意位置 p 的前面插入新的元素 x
void insert_front(int p, int x)
{
    id++;
    e[id] = x;
    mp[x] = id;

    pre[id] = pre[p];
    ne[id] = p;
    ne[pre[p]] = id;
    pre[p] = id;
}

// 删除任意位置 p 的元素
void erase(int p)
{
    mp[e[p]] = 0; // 把标记清空

    ne[pre[p]] = ne[p];
    pre[ne[p]] = pre[p];
}

int main()
{
    for(int i = 1; i <= 5; i++)
    {
        push_front(i);
        print();
    }

    //cout << find(3) << endl;
    //cout << find(5) << endl;
    //cout << find(0) << endl;

    // insert_front(2, 22);
    // print();
    // insert_front(3, 33);
    // print();
    // insert_front(4, 44);
    // print();

    erase(2);
    print();
    erase(4);
    print();

    return 0;
}